import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/2/26 15:33
 * @description 双指针
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1,1,2,2,3,3,4,4,5,5};
        solution.threeSumMulti(arr, 8);
    }
    public int threeSumMulti(int[] arr, int target) {
        int mod = 1_000_000_007;
        int n = arr.length;
        Arrays.sort(arr);
        long ans = 0;
        // 固定a
        for(int i = 0; i < n; i++) {
            int j = i + 1, k = n - 1;
            int sum = target - arr[i];
            while(j < k) {
                if(arr[j] + arr[k] < sum) {
                    j++;
                }else if (arr[j] + arr[k] > sum){
                    k--;
                }else if (arr[j] != arr[k]){
                    int left = 1, right = 1;
                    while (j + 1 < n && arr[j] == arr[j+1]) {
                        // 存在相同元素
                        left++;
                        j++;
                    }
                    while (k - 1 > j  &&  arr[k - 1] == arr[k]) {
                        right++;
                        k--;
                    }
                    ans += (long) left * right;
                    ans %= mod;
                    j++;
                    k--;
                }else {
                    // 两个数相同并且和为sum
                    int M = k-j + 1;
                    ans += (long) M * (M - 1) / 2;
                    ans %= mod;
                    break;
                }

            }
        }
        return (int)ans;
    }
}
